#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <string>
#include <vector>
#include <cctype>
#include <unordered_map>
#include <set>
#include <cmath>
#include <cstdlib> // for system()
#include <chrono> // for std::this_thread::sleep_for
#include <thread> // for std::this_thread
using namespace std;

class Solution1
{
public:
    string modifyString(string s)
    {
        for (int i = 0; i < s.size(); ++i)
        {
            if (s[i] == '?')
            {
                char tmp1 = i - 1 < 0 ? '0' : s[i - 1];
                char tmp2 = i + 1 > s.size() - 1 ? '0' : s[i + 1];
                for (char ch = 'a'; ch <= 'z'; ++ch)
                {
                    if (ch != tmp1 && ch != tmp2)
                    {
                        s[i] = ch;
                    }
                }
            }
        }
        return s;
    }
};

// 提莫攻击
class Solution2
{
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) 
    {
        int ret = 0;
        for(int i=0; i<timeSeries.size(); ++i)
        {
            if(i == timeSeries.size()-1 || timeSeries[i]+duration <= timeSeries[i+1])
            {
                ret +=duration;
            }
            else
            {
                ret += timeSeries[i+1]-timeSeries[i];
            }
        }
        return ret;
    }
};

// Z型变换
class Solution3
{
public:
    string convert(string s, int numRows)
    {
        if (numRows == 1)
            return s;
        int d = 2 * numRows - 2;
        string ret;
        for (int n = 0; n < numRows; n++) // 枚举Z型变换的每一行
        {
            if (n == 0 || n == numRows - 1)
            {
                int i = n;
                while (i < s.size())
                {
                    ret += s[i];
                    i += d;
                }
            }
            else
            {
                int x1 = n;
                int x2 = d - n;
                while (x1 < s.size() && x2 < s.size())
                {
                    ret += s[x1];
                    ret += s[x2];
                    x1 += d;
                    x2 += d;
                }
                // 此时循环结束，但是有可能只是一个判断失败了，但是x1失败了，x2一定失败，所以我们只需要在额外判断一下x1即可
                if (x1 < s.size())
                {
                    ret += s[x1];
                    x1 += d;
                }
            }
        }
        return ret;
    }

    string convert1(string s, int numRows)
    {
        if (numRows == 1) return s;

        vector<vector<char>> vv(numRows, vector<char>(s.size()));
        int x = 0, y = 0, i = 0;
        while (i < s.size())
        {
            if (x < numRows)
            {
                if (x == 0 && isalpha(vv[x][y]) || vv[x][y] == ',' || vv[x][y] == '.')
                {
                    x++;
                }
                while (x < numRows && i < s.size())
                {
                    vv[x++][y] = s[i++];
                }
            }
            else
            {
                if (x == numRows)
                {
                    x = numRows - 1;
                }
                while (x > 0 && i < s.size())
                {
                    vv[--x][++y] = s[i++];
                }
            }
        }
        string ret;
        for (int i = 0; i < numRows; i++)
        {
            for (int j = 0; j < s.size(); j++)
            {
                char ch = vv[i][j];
                if (isalpha(ch) || ch == ',' || ch == '.')
                {
                    ret.push_back(ch);
                }
            }
        }
        return ret;
    }
};

// 模拟——外观数列
class Solution4
{
public:
    string countAndSay(int n)
    {
        string ret = "1";
        for (int i = 1; i < n; i++)
        {
            string tmp;
            int sz = ret.size();
            for (int left = 0, right = 0; right < sz;)
            {
                while (right < sz && ret[left] == ret[right])
                {
                    right++;
                }
                tmp += (right - left) + '0';
                tmp += ret[left];
                left = right;
            }
            ret = tmp;
        }
        return ret;
    }
};

// class Solution 
// {
// public:
//     string countAndSay(int n) 
//     {
//         if (n == 1)
//         {
//             return "1";
//         }

//         string ret = "1";
//         for(int i=2; i<=n; i++)
//         {
//             string tmp;
//             int count = 0;
//             int sz = ret.size();
//             for(int j=0; j<sz; ++j)
//             {
//                 if(j == 0 || ret[j] == ret[j-1])
//                 {
//                     count++;
//                 }
//                 else
//                 {
//                     char c_count = count+'0';
//                     char ch = ret[j-1];
//                     tmp += c_count;
//                     tmp += ch;
//                     count = 1;
//                 }
//             }
//             char c_count = count+'0';
//             char ch = ret[sz-1];
//             tmp += c_count;
//             tmp += ch;
//             ret = tmp;
//         }

//         return ret;
//     }
// };

// 数青蛙
class Solution5
{
public:
    // 写法一：
    int minNumberOfFrogs(string croakOfFrogs)
    {
        string temp = "croak";
        int n = temp.size();
        vector<int> hash(n); // 0~4分别映射c r o a k

        unordered_map<char, int> index; // 记录对应字符在hash中的下标
        for (int i = 0; i < n; i++)
            index[temp[i]] = i;

        for (auto ch : croakOfFrogs)
        {
            if (ch == 'c')
            {
                if (hash[n - 1] != 0) hash[n - 1]--;
                hash[0]++;
            }
            else
            {
                int i = index[ch]; // 当前字符的下标
                if (hash[i - 1] == 0) return -1;
                hash[i - 1]--;
                hash[i]++;
            }
        }
        for (int i = 0; i < hash.size() - 1; i++)
            if (hash[i] != 0) return -1;
        return hash[4];
    }

    // 写法二：if-else
    int _minNumberOfFrogs(string croakOfFrogs)
    {
        int hash[5] = { 0 };// 0~4分别映射c r o a k
        for (auto ch : croakOfFrogs)
        {
            int flag = 0;

            if (ch == 'c')
            {
                flag = 1;
                if (hash[4] != 0) hash[4]--;
                hash[0]++;
            }
            else if (ch == 'r' && hash[0])
            {
                hash[1]++;
                hash[0]--;
                flag = 1;
            }
            else if (ch == 'o' && hash[1])
            {
                hash[2]++;
                hash[1]--;
                flag = 1;
            }
            else if (ch == 'a' && hash[2])
            {
                hash[3]++;
                hash[2]--;
                flag = 1;
            }
            else if (ch == 'k' && hash[3])
            {
                hash[4]++;
                hash[3]--;
                flag = 1;
            }
            if (flag == 0) return -1;
        }
        // 如果遍历完字符串，除k之外的其他字符仍出现了
        // 说明青蛙并没有完整的叫出声，返回-1
        if (hash[0] + hash[1] + hash[2] + hash[3]) return -1;
        return hash[4];
    }
};

struct ListNode 
{
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
    
};

// 删除排序链表中的重复节点
class Solution6
{
public:
    ListNode* deleteDuplicates(ListNode* head)
    {
        if (head == nullptr) return head;

        ListNode* cur = head;
        while (cur->next)
        {
            if (cur->val == cur->next->val)
            {
                cur->next = cur->next->next;
            }
            else
            {
                cur = cur->next;
            }
        }
        return head;
    }

    // ListNode* deleteDuplicates(ListNode* head)
    // {
    //     set<int> unique;
    //     ListNode* cur = head;
    //     while (cur)
    //     {
    //         unique.emplace(cur->val);
    //         cur = cur->next;
    //     }

    //     ListNode* newHead = nullptr;
    //     ListNode* tail = nullptr;
    //     for (auto e : unique)
    //     {
    //         ListNode* newnode = new ListNode(e);
    //         if (newHead == nullptr)
    //         {
    //             newHead = newnode;
    //             tail = newnode;
    //         }
    //         else
    //         {
    //             tail->next = newnode;
    //             tail = newnode;
    //         }
    //     }
    //     return newHead;
    // }
};

// 颜色分类
class Solution7
{
public:
    void sortColors(vector<int>& nums)
    {
        int i = 0, left = -1, right = nums.size();
        while (i < right)
        {
            if (nums[i] == 1) i++;
            else if (nums[i] == 0) swap(nums[++left], nums[i++]);
            else swap(nums[--right], nums[i]);
        }
    }
};

// 排序数组
class Solution8
{
public:
    vector<int> sortArray(vector<int>& nums)
    {
        srand(time(NULL));
        qsort(nums, 0, nums.size() - 1);
        return nums;
    }

    void qsort(vector<int>& nums, int l, int r)
    {
        if (l >= r) return;

        int key = getRandomKey(nums, l, r);
        int i = l, left = l - 1, right = r + 1;
        while (i < right)
        {
            if (nums[i] < key) swap(nums[++left], nums[i++]);
            else if (nums[i] == key) i++;
            else swap(nums[--right], nums[i]);
        }
        // [l,left] [left+1,right] [right,r]
        qsort(nums, l, left);
        qsort(nums, right, r);
    }

    int getRandomKey(vector<int>& nums, int left, int right)
    {
        int r = rand() % (right - left + 1) + left;
        return nums[r];
    }
};

// 快速选择排序——数组中的第k个最大元素
class Solution9
{
public:
    int findKthLargest(vector<int>& nums, int k)
    {
        srand(time(NULL));
        return qsort(nums, 0, nums.size() - 1, k);
    }

    int qsort(vector<int>& nums, int l, int r, int k)
    {
        if (l == r) return nums[l];

        int left = l - 1, right = r + 1, i = l;// 遍历的区间
        int key = getRandomKey(nums, l, r);// 随机基准值
        while (i < right)
        {
            if (nums[i] < key) swap(nums[++left], nums[i++]);
            else if (nums[i] == key) i++;
            else swap(nums[--right], nums[i]);
        }
        int b = right - left - 1, c = r - right + 1;// partion的三个区间的元素个数
        if (c >= k)
            return qsort(nums, right, r, k);
        else if (b + c >= k)
            return key;
        else
            return qsort(nums, l, left, k - b - c);
    }
    int getRandomKey(vector<int>& nums, int l, int r)
    {
        return nums[rand() % (r - l + 1) + l];
    }
};

class Solution10
{
public:
    // 法二： 快速选择算法
    int getRandomPivot(vector<int>& nums, int l, int r)
    {
        return nums[rand() % (r - l + 1) + l];
    }

    vector<int> partition(vector<int>& nums, int l, int r, int pivot)
    {
        int left = l - 1, right = r + 1, i = l;
        while (i < right)
        {
            if (nums[i] < pivot) swap(nums[++left], nums[i++]);
            else if (nums[i] == pivot) i++;
            else swap(nums[--right], nums[i]);
        }
        return { left,right };
    }

    void quick_select(vector<int>& nums, int l, int r, int cnt)
    {
        if (r - l + 1 == cnt) return;

        int pivot = getRandomPivot(nums, l, r);
        vector<int> tmp = partition(nums, l, r, pivot); // 返回left和right的最终位置

        // [l, left] [left + 1, right - 1] [right, r]
        int a = tmp[0] - l + 1, b = tmp[1] - tmp[0] - 1;

        if (a > cnt) return quick_select(nums, l, tmp[0], cnt);
        else if (a + b >= cnt) return;
        else return quick_select(nums, tmp[1], r, cnt - a - b);
    }

    vector<int> inventoryManagement(vector<int>& stock, int cnt)
    {
        srand(time(NULL));
        quick_select(stock, 0, stock.size() - 1, cnt);
        return { stock.begin(),stock.begin() + cnt };
    }


    // 法一：优先队列
    // vector<int> inventoryManagement(vector<int>& stock, int cnt) 
    // {
    //     priority_queue<int, std::vector<int>, greater<int>> heap(stock.begin(),stock.end());
    //     vector<int> ret;
    //     while(cnt--)
    //     {
    //         int x = heap.top();
    //         heap.pop();
    //         ret.emplace_back(x);
    //     }
    //     return ret;
    // }
};


class Solution11
{
    vector<int> tmp;
public:
    void merge(vector<int>& nums, int l, int mid, int r)
    {
        // [l,mid] [mid+1,r]
        int i = l, j = mid + 1, k = 0;
        while (i <= mid && j <= r)
        {
            if (nums[i] < nums[j]) tmp[k++] = nums[i++];
            else tmp[k++] = nums[j++];
        }
        // 循环结束只将一个区间的全部元素插入到tmp中
        // 判断那个区间还有元素，直接将剩余元素都插入到tmp即可
        while (i <= mid) tmp[k++] = (nums[i++]);
        while (j <= r) tmp[k++] = (nums[j++]);

        for (int p = l; p <= r; p++) nums[p] = tmp[p - l];
    }

    void merge_sort(vector<int>& nums, int l, int r)
    {
        if (l >= r) return;

        // 选择中间点
        int mid = (r - l) / 2 + l;

        //[l, mid] [mid+1, r]
        merge_sort(nums, l, mid);
        merge_sort(nums, mid + 1, r);

        // 合并两个有序数组
        merge(nums, l, mid, r);
    }

    vector<int> sortArray(vector<int>& nums)
    {
        tmp.resize(nums.size());
        merge_sort(nums, 0, nums.size() - 1);
        return nums;
    }
};

class Solution12
{
    vector<int> tmp;
public:
    // 策略一：升序数组，找前面有几个比我大的
    int mergeInGreater(vector<int>& nums, int l, int mid, int r)
    {
        // [l,mid] [mid+1,r]
        int ret = 0, i = l, j = mid + 1, k = 0;
        while (i <= mid && j <= r)
        {
            if (nums[i] <= nums[j]) tmp[k++] = nums[i++];
            else
            {
                ret += mid - i + 1;
                tmp[k++] = nums[j++];
            }
        }
        while (i <= mid) tmp[k++] = nums[i++];
        while (j <= r) tmp[k++] = nums[j++];

        for (int p = l; p <= r; p++) nums[p] = tmp[p - l];

        return ret;
    }

    // 策略二：降序数组，找后面有几个比我小的
    int mergeInLess(vector<int>& nums, int l, int mid, int r)
    {
        // [l,mid] [mid+1,r]
        int ret = 0, i = l, j = mid + 1, k = 0;
        while (i <= mid && j <= r)
        {
            if (nums[i] <= nums[j]) tmp[k++] = nums[j++];
            else
            {
                ret += r - j + 1;
                tmp[k++] = nums[i++];
            }
        }
        while (i <= mid) tmp[k++] = nums[i++];
        while (j <= r) tmp[k++] = nums[j++];

        for (int p = l; p <= r; p++) nums[p] = tmp[p - l];

        return ret;
    }

    int merge_sort(vector<int>& nums, int l, int r)
    {
        if (l >= r) return 0;

        int mid = (r - l) / 2 + l;
        // [l,mid] [mid+1,r]

        // 升序
        //return merge_sort(nums,l,mid) + merge_sort(nums,mid+1,r) + mergeInGreater(nums,l,mid,r);

        // 降序
        return merge_sort(nums, l, mid) + merge_sort(nums, mid + 1, r) + mergeInLess(nums, l, mid, r);

    }

    int reversePairs(vector<int>& record)
    {
        tmp.resize(record.size());
        return merge_sort(record, 0, record.size() - 1);
    }
};


class Solution13
{
    vector<int> tmp1;// 临时存储nums
    vector<int> tmp2;// 临时存储index
    vector<int> index;// 数组元素是nums对应元素的下标
    vector<int> ret;
public:
    // 降序，在后面找有多少个比我小
    void mergeInLess(vector<int>& nums, int l, int mid, int r)
    {
        // 合并有序数组
        // index数组也要合并，保证nums与index的对应关系
        int i = l, j = mid + 1, k = 0;
        while (i <= mid && j <= r)
        {
            if (nums[i] <= nums[j])
            {
                tmp1[k] = nums[j];
                tmp2[k++] = index[j++];
            }
            else
            {
                ret[index[i]] += r - j + 1;
                tmp1[k] = nums[i];
                tmp2[k++] = index[i++];
            }
        }

        while (i <= mid)
        {
            tmp1[k] = nums[i];
            tmp2[k++] = index[i++];
        }

        while (j <= r)
        {
            tmp1[k] = nums[j];
            tmp2[k++] = index[j++];
        }

        // 覆盖原数组
        for (int p = l; p <= r; p++)
        {
            nums[p] = tmp1[p - l];
            index[p] = tmp2[p - l];
        }
    }

    void merge_sort(vector<int>& nums, int l, int r)
    {
        if (l >= r) return;

        int mid = (r - l) / 2 + l;
        // [l,mid] [mid+1,r]
        merge_sort(nums, l, mid);
        merge_sort(nums, mid + 1, r);

        mergeInLess(nums, l, mid, r);
    }

    vector<int> countSmaller(vector<int>& nums)
    {
        if (nums.size() == 1) return { 0 };

        tmp1.resize(nums.size());
        tmp2.resize(nums.size());
        index.resize(nums.size());
        ret.resize(nums.size());
        for (int i = 0; i < nums.size(); ++i) index[i] = i;

        merge_sort(nums, 0, nums.size() - 1);
        return ret;
    }
};


class Solution14
{
    vector<int> tmp;
public:
    int mergeInLess(vector<int>& nums, int left, int mid, int right)
    {
        int ret = 0;

        // 借助tmp排序区间
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) // 降序
        {
            if (nums[i] < nums[j]) tmp[k++] = nums[j++];
            else// nums[i] > nums[j]
            {
                if ((long long)nums[i] > (long long)2 * nums[j]) ret += right - j + 1;
                else// nums[i] <= 2*nums[j] ，但是右区间后面的元素还有可能满足nums[i] < nums[j]*2的关系
                // 所以，当目前只大于1倍时不能直接将i位置插入到tmp中，先让i与j后面的元素比较，比较完之后，再将i位置的元素插入到tmp中
                {
                    int t = j + 1;
                    while (t <= right)
                    {
                        if ((long long)nums[i] > (long long)2 * nums[t])
                        {
                            ret += right - t + 1;
                        }
                        t++;
                    }
                }
                tmp[k++] = nums[i++];
            }
        }

        // 处理没有排序的区间
        while (i <= mid) tmp[k++] = nums[i++];
        while (j <= right) tmp[k++] = nums[j++];

        // 覆盖原数组，使原数组有序
        for (int i = left; i <= right; ++i)
            nums[i] = tmp[i - left];

        return ret;
    }

    int merge_sort(vector<int>& nums, int left, int right)
    {
        if (left >= right) return 0;

        int ret = 0;

        // 划分区间
        // [left,mid] [mid+1,right]
        int mid = (right - left) / 2 + left;

        // 处理左区间
        ret += merge_sort(nums, left, mid);

        // 处理右区间
        ret += merge_sort(nums, mid + 1, right);

        // 处理一左一右
        ret += mergeInLess(nums, left, mid, right);

        return ret;
    }

    int reversePairs(vector<int>& nums)
    {
        tmp.resize(nums.size());
        return merge_sort(nums, 0, nums.size() - 1);
    }
};

// 翻转对——在合并数组前先计算翻转对
class Solution14_2
{
    vector<int> tmp;
public:
    void mergeInLess(vector<int>& nums, int left, int mid, int right)
    {
        // 借助tmp排序区间
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) // 降序
        {
            if (nums[i] <= nums[j]) tmp[k++] = nums[j++];
            else// nums[i] > nums[j]
            {
                tmp[k++] = nums[i++];
            }
        }

        // 处理没有排序的区间
        while (i <= mid) tmp[k++] = nums[i++];
        while (j <= right) tmp[k++] = nums[j++];

        // 覆盖原数组，使原数组有序
        for (int i = left; i <= right; ++i)
            nums[i] = tmp[i - left];
    }

    int getreversePairs(vector<int>& nums, int left, int mid, int right)
    {
        int ret = 0;
        int left_index = left, right_index = mid + 1;
        while (left_index <= mid) // 降序
        {
            while (right_index <= right && nums[left_index] / 2.0 <= nums[right_index]) right_index++;
            if (right_index > right)
                break;
            ret += right - right_index + 1;
            left_index++;
        }
        return ret;
    }

    int merge_sort(vector<int>& nums, int left, int right)
    {
        if (left >= right) return 0;
        int ret = 0;

        // 划分区间
        // [left,mid] [mid+1,right]
        int mid = (right - left) / 2 + left;

        // 处理左区间
        ret += merge_sort(nums, left, mid);

        // 处理右区间
        ret += merge_sort(nums, mid + 1, right);

        //获取翻转对
        ret += getreversePairs(nums, left, mid, right);

        // 合并有序数组
        mergeInLess(nums, left, mid, right);

        return ret;
    }

    int reversePairs(vector<int>& nums)
    {
        tmp.resize(nums.size());
        return merge_sort(nums, 0, nums.size() - 1);
    }
};


void heart() 
{
    int width = 40; // 爱心的宽度
    int height = 20; // 爱心的高度
    double aspect_ratio = static_cast<double>(width) / height;

    for (int y = height; y >= -height; --y) {
        for (int x = -width; x <= width; ++x) {
            // 使用心形公式 (x^2 + y^2 - 1)^3 - x^2 * y^3 <= 0
            double formula = pow(x * aspect_ratio / 16.0, 2) + pow(y / 16.0, 2) - 1;
            if (formula * formula * formula - pow(x * aspect_ratio / 16.0, 2) * pow(y / 16.0, 3) <= 0) {
                cout << "*";
            }
            else {
                cout << " ";
            }
        }
        cout << endl;
    }
}

//int main()
//{
//    heart();
//
//    //vector<int> v{2,4,3,5,1};
//    //int ret = Solution14().reversePairs(v);
//
//    //vector<int> ret = Solution13().countSmaller(v);
//
//    //int ret = Solution12().reversePairs(v);
//
//    //vector<int> ret = Solution11().sortArray(v);
//
//    //vector<int> v{ 0,2,3,6 };
//    //vector<int> ret = Solution10().inventoryManagement(v, 2);
//
//    //ListNode* head = new ListNode(1);
//    //ListNode* node1 = new ListNode(1);
//    //ListNode* node2 = new ListNode(2);
//    //ListNode* node3 = new ListNode(3);
//    //ListNode* node4 = new ListNode(3);
//    //head->next = node1;
//    //node1->next = node2;
//    //node2->next = node3;
//    //node3->next = node4;
//
//    //Solution6().deleteDuplicates(head);
//
//    //Solution5().minNumberOfFrogs("croakcroak");
//
//    //cout << Solution4().countAndSay(1) << endl;
//    //cout << Solution4().countAndSay(4) << endl;
//    //cout << Solution4().countAndSay(6) << endl;
//    //cout << Solution3().convert("PAYPALISHIRING", 3) << endl;
//    //cout << Solution3().convert("Apalindromeisaword,phrase,number,orothersequenceofunitsthatcanbereadthesamewayineitherdirection,withgeneralallowancesforadjustmentstopunctuationandworddividers.", 2);
//    return 0;
//}

void clearScreen() {
#ifdef _WIN32
    system("cls");
#else
    system("clear");
#endif
}

int main() {
    const int width = 60;  // 爱心的宽度，根据屏幕尺寸调整
    const int height = 30; // 爱心的高度，根据屏幕尺寸调整
    const double scale = 15.0; // 调整心形大小的缩放因子
    const int frames = 10; // 动画帧数
    const int delay = 150; // 每帧之间的延迟时间（毫秒）

    for (int frame = 0; frame < frames; ++frame) {
        clearScreen();

        for (int y = height; y >= -height; --y) {
            for (int x = -width; x <= width; ++x) {
                // 使用心形公式，并添加一些动态效果（通过frame变量）
                double formula = pow((x * scale / width + frame * 0.1) / scale, 2)
                    + pow((y * scale / height) / scale, 2) - 1;
                if (formula * formula * formula - pow((x * scale / width + frame * 0.1) / scale, 2)
                    * pow((y * scale / height) / scale, 3) <= 0) {
                    cout << "*";
                }
                else {
                    cout << " ";
                }
            }
            cout << endl;
        }

        // 延迟一段时间以创建动画效果
        this_thread::sleep_for(chrono::milliseconds(delay));
    }

    return 0;
}